在许多应用中，二叉搜索树可以工作得很好，然而在最差情况下（插入一个有序序列），它的性能得不到保证。下面介绍一种平衡搜索树，可以在任何情况下保证 O(logN) 的时间复杂度。
理想情况下，我们希望树的形状是完美平衡的，这样的话，查找效率就是 O(lgN)；然而，对于不可预料的动态插入操作，保持树形状完美平衡的开销太大。我们稍稍放松对完美平衡的要求，便可以对所有操作提供 O(logN) 的保证
2-3搜索树（2-3 search trees）
我们现在允许树的一个节点中有两个值（Key），连接着三个子节点（Link），将这样的节点称为3-节点，原来那样的节点称为2-节点。
————————————————————————
一个2-3搜索树要么是空的，要么是：
一个 2-节点，左链接连接着一棵2-3搜索树（所有的值小于当前节点的值），右链接连接着一棵2-3搜索树（所有的值大于当前结点的值）
一个 3-节点，左链接连接着一棵2-3搜索树（所有的值小于当前节点中较小的那个值），中链接连接着一棵2-3搜索树（所有值在当前结点两个值之间），右链接连接着一棵2-3搜索树（所有的值大于当前结点较大的那个值）
————————————————————————
如果一个2-3搜索树的所有空链接到根节点的距离都相等，那么我们就说这棵2-3搜索树是平衡的。
————————————————————————
搜索（Search）
从根节点开始向下比较，如果与节点中任一值相等，则搜索命中；如果不相等，我们按照左中右连接进行分流；如果遇到空节点，则说明查找失败。
插入到一个 2-节点 中（Insert into a 2-node）
用一个 3-节点 替换掉原来的 2-节点
插入到只含一个3-节点的2-3树中（Insert into a tree consisting of a single 3-node）
把3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点
插入到一个父节点是2-节点的3-节点中（Insert into a 3-node whose parent is a 2-node）
把3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点，将父节点变为一个3-节点
插入到一个父节点是3-节点的3-节点中（Insert into a 3-node whose parent is a 3-node）
向上把每个3-节点变成一个暂时的4-节点，然后把这个4-节点分成三个2-节点，将父节点变为一个暂时的4-节点。由此向上，直到遇到一个2-节点，或到根节点时让整个树增加1层。
怎样分开一个4-节点
————————————————————————
对于一个含有N个元素的2-3树，搜索和插入操作保证最多访问 lgN 个节点
————————————————————————
红黑树（Red-Black BSTs）
编码 3-节点
最自然的方法是利用二分查找树(BST)，然后添加一些信息来标记 3-节点
我们把链接分为两种：
- 红链接(Red Link)：连接着两个2-节点来表示一个3-节点
- 黑链接(Black Link)：和BST的链接一样，连接着2-3树
特别地，我们用向左倾斜的红链接连接着的两个2-节点来表示一个3-节点
————————————————————————
红黑树是满足下列调节的具有红黑链接的二叉树：
- 红链接向左倾斜
- 没有一个节点连接着两条红链接
- 红黑树是平衡的：每个空链接到根节点的路径上有相同数量的黑链接
————————————————————————
红黑树即是2-3树，也是BST，所以它结合了BST的高效搜索方法和2-3树的平衡插入特点
颜色表示
在节点的定义里加入一个 bool 变量来表示当前结点与父节点的链接是不是红链接
旋转（Rotation）
在红黑书的实现中，我们暂时允许以下情况：
- 向右倾斜的红链接
- 一个节点连接着两个红链接
我们用旋转来修正第一种情况
Node rotateLeft(Node h)
{
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
Node rotateRight(Node h)
{
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1 + size(h.left) + size(h.right);
return x;
}
插入到一个 2-节点 中（Insert into a 2-node）
如果新插入的节点比原来的节点小，则将它正常插入，然后把新节点的颜色设为红色；如果比原来的大，则正常插入，把新节点的颜色设置为红色，然后进行一次左旋转。
插入到只含一个3-节点的2-3树中（Insert into a tree consisting of a single 3-node）
void flipColors(Node h)
{
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
保持根节点是黑色的
上面的代码有可能会使根节点的颜色变为红色，所以每次插入操作后，我们要让根节点的颜色变回黑色。注意到，每当根节点颜色变红时，树的高度就增加了1。
插入到一个位于底部的 3-节点中（Insert into a 3-node at the bottom）
相当于将一个新的红链接逐层向上传递，直到符合顺序（没有右倾斜的红链接，没有两个红链接连着同一个节点等），或到达根节点。
插入操作的实现
public void put(Key key, Value val)
{
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val)
{
if (h == null) return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}